package dynamicProgramming.bagQuestion;

public class Class518 {

//    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
    public int change(int amount, int[] coins) {
            int[][] dp = new int[coins.length][amount + 1];
            // 只有一种硬币的情况
            for (int i = 0; i <= amount; i += coins[0]) {
                dp[0][i] = 1;
            }
            for (int i = 1; i < coins.length; i++) {
                for (int j = 0; j <= amount; j++) {
                    // 第i种硬币使用0~k次，求和
                    for (int k = 0; k * coins[i] <= j; k++) {
                        dp[i][j] += dp[i - 1][j - k * coins[i]];
                    }
                }
            }
            return dp[coins.length - 1][amount];
        }



    public int backPackV(int[] nums, int target) {
        // write your code here

        int[][]dp=new int[nums.length+1][target+1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0]=1;
        }
        for (int index = 1; index<=nums.length; index++) {
            for (int rest = 1; rest <=target; rest++) {
//                if (nums[index-1]>rest){
//                    dp[index][rest]=dp[index-1][rest];
//                }else {
//                    dp[index][rest]=Math.max(nums[index-1]+dp[index-1][rest-nums[index-1]],dp[index-1][rest]);
//                }
                dp[index][rest]=dp[index-1][rest];


                if (rest>=nums[index-1]){
                    //TODO:2024/1/24  rest-nums[index-1]  这个部分控制使得刚好装满
                    dp[index][rest]+=dp[index-1][rest-nums[index-1]];
                }


            }
        }
        return  dp[nums.length][target];



    }

}
